home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / c_lang / z150_src.lzh / LZD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-07-12  |  7.1 KB  |  239 lines
  1. #ifndef LINT
  2. /* @(#) lzd.c 1.5 87/05/29 12:54:10 */
  3. static char sccsid[]="@(#) lzd.c 1.5 87/05/29 12:54:10";
  4. #endif /* LINT */
  5.  
  6. #include "options.h"
  7. /*
  8. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  9. code.  The contents of this file are hereby released to the public domain.
  10.                                  -- Rahul Dhesi 1986/11/14
  11. */
  12.  
  13. #include <stdio.h>            /* just to define NULL */
  14. #include "various.h"
  15. #include "zoofns.h"           /* function definitions */
  16. /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
  17. #include "zoomem.h"
  18. #include "debug.h"
  19. #include "assert.h"
  20. /* lzconst.h contains constants for lzd() and lzc() */
  21. #include "lzconst.h"
  22.  
  23. #define  STACKSIZE   4000
  24.  
  25. struct tabentry {
  26.    unsigned next;
  27.    char z_ch;
  28. };
  29.  
  30. void init_dtab();
  31. unsigned rd_dcode();
  32.  
  33. #ifdef LINT_ARGS
  34. void wr_dchar (char);
  35. #else
  36. void wr_dchar();
  37. #endif
  38.  
  39. void ad_dcode();
  40.  
  41. static unsigned stack_pointer = 0;
  42. static unsigned *stack;
  43.  
  44. #define  push(x)  {  \
  45.                      stack[stack_pointer++] = (x);                   \
  46.                      if (stack_pointer >= STACKSIZE)                 \
  47.                         prterror ('f', "Stack overflow in lzd().\n");\
  48.                   }
  49. #define  pop()    (stack[--stack_pointer])
  50.  
  51. extern char *out_buf_adr;        /* output buffer */
  52. extern char *in_buf_adr;         /* input buffer */
  53.  
  54. char memflag = 0;                /* memory allocated? flag */
  55. extern struct tabentry *table;   /* hash table from lzc.c */
  56. static unsigned cur_code;
  57. static unsigned old_code;
  58. static unsigned in_code;
  59.  
  60. static unsigned free_code;
  61. static int nbits;
  62. static unsigned max_code;
  63.  
  64. static char fin_char;
  65. static char k;
  66. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  67.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  68. static unsigned bit_offset;
  69. static unsigned output_offset;
  70. static int in_han, out_han; 
  71.  
  72. int lzd(input_handle, output_handle)
  73. int input_handle, output_handle;          /* input & output file handles */
  74. {
  75.    in_han = input_handle;                 /* make it avail to other fns */
  76.    out_han = output_handle;               /* ditto */
  77.    nbits = 9;
  78.    max_code = 512;
  79.    free_code = FIRST_FREE;
  80.    stack_pointer = 0;
  81.    bit_offset = 0;
  82.    output_offset = 0;
  83.  
  84.    if (read(in_han, in_buf_adr, INBUFSIZ) == -1)
  85.       return(IOERR);
  86.    if (memflag == 0) {
  87.      table = (struct tabentry *) emalloc((MAXMAX+10) * sizeof(struct tabentry));
  88.      stack = (unsigned *) emalloc (sizeof (unsigned) * STACKSIZE + 20);
  89.      memflag++;
  90.    }
  91.  
  92.    init_dtab();             /* initialize table */
  93.  
  94. loop:
  95.    cur_code = rd_dcode();
  96.    if (cur_code == Z_EOF) {
  97.       debug((printf ("lzd: Z_EOF\n")))
  98.       if (output_offset != 0) {
  99.          if (out_han != -2) {
  100.             if (write(out_han, out_buf_adr, output_offset) != output_offset)
  101.                prterror ('f', "Output error in lzd().\n");
  102.          }
  103.          addbfcrc(out_buf_adr, output_offset);
  104.       }
  105.       return (0);
  106.    }
  107.  
  108.    assert(nbits >= 9 && nbits <= 13);
  109.  
  110.    if (cur_code == CLEAR) {
  111.       debug((printf ("lzd: CLEAR\n")))
  112.       init_dtab();
  113.       fin_char = k = old_code = cur_code = rd_dcode();
  114.       wr_dchar(k);
  115.       goto loop;
  116.    }
  117.  
  118.    in_code = cur_code;
  119.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  120.       cur_code = old_code;             /* previous code becomes current */
  121.       push(fin_char);
  122.    }
  123.  
  124.    while (cur_code > 255) {               /* if code, not character */
  125.       push(table[cur_code].z_ch);         /* push suffix char */
  126.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  127.    }
  128.  
  129.    assert(nbits >= 9 && nbits <= 13);
  130.  
  131.    k = fin_char = cur_code;
  132.    push(k);
  133.    while (stack_pointer != 0) {
  134.       wr_dchar(pop());
  135.    }
  136.    assert(nbits >= 9 && nbits <= 13);
  137.    ad_dcode();
  138.    old_code = in_code;
  139.  
  140.    assert(nbits >= 9 && nbits <= 13);
  141.  
  142.    goto loop;
  143. } /* lzd() */
  144.  
  145. /* rd_dcode() reads a code from the input (compressed) file and returns
  146. its value. */
  147. unsigned rd_dcode()
  148. {
  149.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  150.    unsigned word;                     /* first 16 bits in buffer */
  151.    unsigned byte_offset;
  152.    char nextch;                           /* next 8 bits in buffer */
  153.    unsigned ofs_inbyte;               /* offset within byte */
  154.  
  155.    ofs_inbyte = bit_offset % 8;
  156.    byte_offset = bit_offset / 8;
  157.    bit_offset = bit_offset + nbits;
  158.  
  159.    assert(nbits >= 9 && nbits <= 13);
  160.  
  161.    if (byte_offset >= INBUFSIZ - 5) {
  162.       int space_left;
  163.  
  164.       assert(byte_offset >= INBUFSIZ - 5);
  165.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  166.  
  167.       bit_offset = ofs_inbyte + nbits;
  168.       space_left = INBUFSIZ - byte_offset;
  169.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  170.       ptra = in_buf_adr;
  171.       /* we now move the remaining characters down buffer beginning */
  172.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  173.       while (space_left > 0) {
  174.          *ptra++ = *ptrb++;
  175.          space_left--;
  176.       }
  177.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  178.       assert(space_left == 0);
  179.       if (read(in_han, ptra, byte_offset) == -1)
  180.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  181.       byte_offset = 0;
  182.    }
  183.    ptra = byte_offset + in_buf_adr;
  184.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  185.    word = (unsigned char) *ptra; ptra++;
  186.    word = word | ((unsigned char) *ptra) << 8; ptra++;
  187.  
  188.    nextch = *ptra;
  189.    if (ofs_inbyte != 0) {
  190.       /* shift nextch right by ofs_inbyte bits */
  191.       /* and shift those bits right into word; */
  192.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  193.    }
  194.    return (word & masks[nbits]); 
  195. } /* rd_dcode() */
  196.  
  197. void init_dtab()
  198. {
  199.    nbits = 9;
  200.    max_code = 512;
  201.    free_code = FIRST_FREE;
  202. }
  203.  
  204. void wr_dchar (ch)
  205. char ch;
  206. {
  207.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  208.       if (out_han != -2) {
  209.          if (write(out_han, out_buf_adr, output_offset) != output_offset)
  210.             prterror ('f', "Write error in lzd:wr_dchar.\n");
  211.       }
  212.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  213.       output_offset = 0;                  /* restore empty buffer */
  214.    }
  215.    assert(output_offset < OUTBUFSIZ);
  216.    out_buf_adr[output_offset++] = ch;        /* store character */
  217. } /* wr_dchar() */
  218.  
  219. /* adds a code to table */
  220. void ad_dcode()
  221. {
  222.    assert(nbits >= 9 && nbits <= 13);
  223.    assert(free_code <= MAXMAX+1);
  224.    table[free_code].z_ch = k;                /* save suffix char */
  225.    table[free_code].next = old_code;         /* save prefix code */
  226.    free_code++;
  227.    assert(nbits >= 9 && nbits <= 13);
  228.    if (free_code >= max_code) {
  229.       if (nbits < MAXBITS) {
  230.          debug((printf("lzd: nbits was %d\n", nbits)))
  231.          nbits++;
  232.          assert(nbits >= 9 && nbits <= 13);
  233.          debug((printf("lzd: nbits now %d\n", nbits)))
  234.          max_code = max_code << 1;        /* double max_code */
  235.          debug((printf("lzd: max_code now %d\n", max_code)))
  236.       }
  237.    }
  238. }
  239.